package com.hss.questions.arr;
/**
 http://www.cyc2018.xyz/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87%20Offer%20%E9%A2%98%E8%A7%A3/4.%20%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E6%9F%A5%E6%89%BE.html#%E9%A2%98%E7%9B%AE%E9%93%BE%E6%8E%A5

 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

 要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。


* */
public class Search2DArray {

    public static int[][] arr = {
            {1, 4, 7, 11, 15},
            {2, 5, 8, 12, 19},
            {3, 6, 9, 16, 22},
            {10, 13, 14, 17, 24},
            {18, 21, 23, 26, 30}
    };

    public static void main(String[] args) {
        boolean result = find(23, arr);
        System.out.println("result = "+result);
    }

    public static boolean find(int target, int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;

        int col =  matrix[0].length;
        int row =  matrix.length;
//        System.out.printf("col = "+col);
//        System.out.printf("row = "+row);
        int r =0,c=col-1;
        while (r<row && c>=0){
            if (matrix[r][c] == target){
                return  true;
            }else if (matrix[r][c] > target){
                c--;
            }else {
                r++;
            }
        }

        return false;
    }

}
